package com.test.demo.algorithm.sort;

public class BubleSort {

    /**
     * 两次循环
     * 比较相邻的元素如果后者比前者小，则交换位置
     * 现象：依次找出最大的值放到最右边
     * 16s
     * @param array
     * @return
     */
    public static int[] bubleSort(int[] array) {
        int count=0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 1; j < array.length - i; j++) {
                if (array[j] < array[j - 1]) {
                    array[j] = array[j] ^ array[j - 1];
                    array[j - 1] = array[j - 1] ^ array[j];
                    array[j] = array[j] ^ array[j - 1];
                }
                count++;
            }
        }
        //System.out.println("比较次数:"+count);
        return array;
    }

    /**
     * 进行优化
     * 如果后面这一段已经是排好序的了就不用接着比较了，添加一个flag来判断
     * 16s
     * @param array
     * @return
     */
    public static int[] bubleSort2(int[] array) {
        int count=0;
        for (int i = 0; i < array.length; i++) {
            boolean flag=true;
            for (int j = 1; j < array.length - i; j++) {
                if (array[j] < array[j - 1]) {
                    array[j] = array[j] ^ array[j - 1];
                    array[j - 1] = array[j - 1] ^ array[j];
                    array[j] = array[j] ^ array[j - 1];
                    flag=false;
                }
                count++;
            }
            if (flag){
                break;
            }
        }
        //System.out.println("比较次数:"+count);
        return array;
    }
}
